/* 	
 This is ol' doubly-linked list implementation
 It works funny but it does.
 If you use it please don't remove my humble name n address
 Alexey Serikov <kompadre(random at)gmail.com>
 */

#include "amever.h"

struct chain_node *chain_nodeInit(struct chain_set *parent, void *val,
		unsigned int pos, struct chain_node *me) {
	if (!parent)
		return 0;
	if (parent->maxlen <= parent->len) {
		amelog("Cannot add %dnth node to %ded chain.\n", parent->len,
				parent->maxlen);
		return 0;
	}
	if (!me) {
		me = chain_getNode();
		me->parent = parent;
		me->index = pos;
		me->val = val;
	}

	if (pos == 0 || parent->first == 0 || pos < parent->first->index) {
		if (parent->first) {
			CHAIN_PUSHB(parent->first, me);
		} else {
			parent->first = me;
			parent->last = me;
			me->next = 0;
			me->prev = 0;
			me->parent = parent;
			me->parent->len++;
		}
	} else if (pos >= parent->last->index) {
		_CHAIN_PUSHA(parent->last, me);
	} else {
		register struct chain_node *noderator;
		register short unsigned i;
		unsigned int bestres = (parent->last->index - pos) > (pos - parent->first->index) ? (pos - parent->first->index) : (parent->last->index - pos);
		noderator = (parent->last->index - pos) > (pos - parent->first->index) ? parent->first : parent->last;
		if (parent->len > MILE) {
			for (i=0; i<CHAIN_MILESTONES; i++) {
				if (noderator && parent->milestones[i]
						&& (unsigned)parent->milestones[i]->index - pos
								< bestres) {
					bestres = (unsigned)parent->milestones[i]->index - pos;
					noderator = parent->milestones[i];
				}
			}
		}
		register int _MILE = (int)(parent->len / CHAIN_MILESTONES);
		if (noderator->index < pos) {
			for (i=0; noderator->index < pos; noderator = noderator->next, i++) {
				if (noderator && i && _MILE && !(i % _MILE )) {
					parent->milestones[(unsigned int)(i % CHAIN_MILESTONES)] = noderator;
					noderator->milestone = 1;
				}
			}
			if (noderator) {
				CHAIN_PUSHB(noderator, me);
			}
		} else {
			for (i=0; noderator->index > pos; noderator = noderator->prev, i++) {
				if (noderator && i && _MILE && !(i % _MILE )) {
					parent->milestones[(unsigned int)(i % CHAIN_MILESTONES)] = noderator;
					noderator->milestone = 1;
				}
			}
			if (noderator) {
				CHAIN_PUSHA(noderator, me);
			}
		}
		if (!me->parent) {
			chain_nodeShut(me);
			me = 0;
		}
	}
	if (!me) {
		amelog("node init failed.\n");
		return NULL;
	}
	return me;
}

int chain_nodeShut(struct chain_node *me) {
	if (me == NULL || !me)
		return 0;
	if (me->milestone)
		memset(me->parent->milestones, 0, sizeof(me->parent->milestones));
	CHAIN_UNLINK(me);
	if (me->parent == s.freeNodes || s.freeNodes->len > s.freeNodes->maxlen) {
		amelog("Freeing...\n");
		free(me);
	} else {
		memset(me, 0, sizeof(struct chain_node));
		amelog("Me->parent == %p, Me == %p.\n", me->parent, me);
		if (s.freeNodes->last) {
			amelog("PUSHING B\n");
			_CHAIN_PUSHA(s.freeNodes->last, me);
		} else {
			amelog("PUSHING A\n");
			me->parent = s.freeNodes;
			me->parent->first = me;
			me->parent->last = me;
			me->parent->len++;
		}
	}
	return 1;
}

void chain_nodeShutI(struct chain_node *me) {
	memset(me, 0, sizeof(struct chain_node));
	if (s.freeNodes->len > s.freeNodes->maxlen) {
		free(me);
	} else if ((s.freeNodes->first) && (s.freeNodes->last)) {
		me->prev = s.freeNodes->last;
		s.freeNodes->last->next = me;
		s.freeNodes->last = me;
		s.freeNodes->len++;
	} else {
		s.freeNodes->last =s.freeNodes->first = me;
		s.freeNodes->len = 1;
	}
}

struct chain_set * chain_setInit(void *p, int type, int maxlen) {
	struct chain_set *me = malloc(sizeof(struct chain_set) + 255); // freed int chain_setShut
	me->last = NULL;
	me->first = NULL;
	me->len = 0;
	me->contiguous = 1;
	me->val = (void *)p;

	if (maxlen == 0) {
		me->maxlen = 0xFF;
	} else {
		me->maxlen = maxlen;
	}
	return me;
}

void chain_setShutFreePointers(struct chain_set *me) {

	if (me && me->first) {
		struct chain_node *noderator = me->first;
		struct chain_node *tmp;
		do {
			tmp = noderator;
			if (tmp && tmp->val)
				free(tmp->val);
			noderator = noderator->next;
			chain_nodeShut(tmp);
		} while (noderator);
	}
	if (me)
		free(me);
}

void chain_setShut(struct chain_set *me) {
	chain_setClear(me);
	free(me);
	me = 0;
}

void chain_setClear(struct chain_set *me) {
	if (!me)
		return;
#ifdef CHAIN_SETCLEAR_FAST
	if (s.freeNodes->len < s.freeNodes->maxlen) {
		if (s.freeNodes->first && s.freeNodes->last && s.freeNodes->len) {

			s.freeNodes->last->next = me->first;
			s.freeNodes->last = me->last;
			s.freeNodes->len += me->len;
		}
		else {
			s.freeNodes->first = me->first;
			s.freeNodes->last = me->last;
			s.freeNodes->len = me->len;
		}
		me->first = me->last = NULL;
		me->len = 0;
	}
	else {
#endif
	struct chain_node *noderator = me->first;
	struct chain_node *tmp;
	while (noderator) {
		tmp = noderator;
		noderator = noderator->next;
		chain_nodeShut(tmp);
	}
	chain_nodeShut(noderator);
	me->len = 0;
	me->first = me->last = 0;
#ifdef CHAIN_SETCLEAR_FAST
}
#endif
}

struct chain_node *chain_insertUnique(struct chain_set *set, int pos,
		void *val, unsigned char replace) {
	struct chain_node *node = chain_findIndex(set, pos);
	if (!node) {
		node = chain_getNode();
		node->index = pos;
		node->val = val;
		node->parent = set;
		node->parent->first = node->parent->last = node;
		node->next = node->prev = 0;
		set->len++;
		return node;
	} else if (node->index == pos) {
		if (replace) {
			node->val = val;
			return node;
		}
		return 0;
	}

	struct chain_node *result = chain_getNode();
	result->val = val;
	result->index = pos;

	if (node->index > pos) {
		CHAIN_PUSHB(node, result);
	} else {
		CHAIN_PUSHA(node, result);
	}
	result->parent = set;
	return result;
}

struct chain_node *chain_getNode(void) {
	struct chain_node *result;
	if (s.freeNodes->first) {
		result = s.freeNodes->first;
		CHAIN_UNLINK(result);
	}
	else 
	{
		result = malloc(sizeof(struct chain_node));
		memset(result, 0, sizeof(struct chain_node));
	}
	return result;
}

struct chain_node *chain_findExactIndex(struct chain_set *parent, int pos) {
	struct chain_node *node = chain_findIndex(parent, pos);
	if (node && node->index == pos)
		return node;
	else
		return 0;
}

struct chain_node *chain_findIndex(struct chain_set *parent, int pos) {
	/* Very relatively quick find, returns the first nearest element, supposingly */
	if (parent == NULL || parent->first == NULL)
		return 0;
	if (pos < parent->first->index)
		return parent->first;
	if (pos > parent->last->index)
		return parent->last;

	if (parent->first == NULL || pos <= parent->first->index) {
		return parent->first;
	} else if (pos >= parent->last->index) {
		return parent->last;
	} else if (parent->len < MILE) {
		struct chain_node *noderator = (parent->last->index - pos) > (pos
				- parent->first->index) ? parent->first : parent->last;
		if (parent->last->index - pos > pos - parent->first->index) {
			for (noderator = parent->first; noderator && noderator->index < pos; noderator = noderator->next);
		} else {
			for (noderator = parent->last; noderator && noderator->index > pos; noderator= noderator->prev);
		}
		return noderator;
	} else {
		struct chain_node *noderator;
		int i;
		unsigned int bestres = (parent->last->index - pos) > (pos
				- parent->first->index) ? (pos - parent->first->index)
				: (parent->last->index - pos);
		noderator
				= (parent->last->index - pos) > (pos - parent->first->index) ? parent->first
						: parent->last;

		for (i=1; i<CHAIN_MILESTONES && parent->milestones[i] > 0; i++) {
			if (parent->milestones[i] && (unsigned)parent->milestones[i]->index
					- pos < bestres) {
				bestres = (unsigned)parent->milestones[i]->index - pos;
				noderator = parent->milestones[i];
			}
		}

		int _MILE = (int)(parent->len / CHAIN_MILESTONES);

		if (noderator->index < pos) {
			for (i=0; noderator->index < pos; noderator = noderator->next, i++) {
				if (noderator && i && _MILE && !(i % _MILE )) {
					parent->milestones[(unsigned int)(i % CHAIN_MILESTONES)] = noderator;
					noderator->milestone = 1;
				}
			}
		} else {
			for (i=0; noderator->index > pos; noderator = noderator->prev, i++) {
				if (noderator && i && _MILE && !(i % _MILE )) {
					parent->milestones[(unsigned int)(i % CHAIN_MILESTONES)] = noderator;
					noderator->milestone = 1;
				}
			}
		}
		return noderator;
	}
	return 0;
}

void _CHAIN_PUSHA(struct chain_node *node, struct chain_node *me)
{
	me->parent = node->parent;
	me->parent->len++;
	me->prev = node;
	me->next = node->next;
	node->next = me;
	if (node == node->parent->last)
		node->parent->last = me;
	
	if (me->next) {
		me->next->prev = me;
	}
	else {
		me->parent->last = me;
	}
}


struct chain_set *chain_setInvert(struct chain_set *old) {
	struct chain_set *newset = chain_setInit(0, 0, 255);
	struct chain_node *node;
	for (node=old->last; node; node=node->prev)
		chain_nodeInit(newset, node->val, 1, 0);
	return newset;
}
